1. Field of the Invention
This invention relates to a system and method of estimating time delay in integrated circuit design in general, and, in particular, to a system and method for estimating the interconnect delay in a Very Large System Integration (VLSI) circuit.
2. Description of the Related Art
VLSI circuits are commonplace in processor chips, whether for microprocessors, embedded devices, Digital Signal Processors (DSPs), etc. VLSI circuits are designed by groups of engineers who prepare detailed layout drawings, usually using Computer Aided Design (CAD) tools. These layouts macroscopically present the extremely complex pattern of active elements (such as transistors) and passive elements (such as interconnects) which, when photo-etched, doped, and deposited onto a silicon matrix, will collectively constitute the finished chip, which may include millions of microscopic parts, all interconnected according to a design.
The sequence of manufacturing steps required to produce such a VLSI chip in quantity is correspondingly complex. Thus, from initial design to setup of the manufacturing line, introduction of a new VLSI chip is an extremely expensive process, and not to be initiated lightly.
A major technical consideration underlying any new chip design is the maximum clock frequency at which the chip will operate in situ. If the frequency must, for the particular application, be greater that that at which a chip according to the particular design can operate, failure of the chip to function properlyxe2x80x94or literal failure of the chipxe2x80x94can be the result.
It is important, therefore, in the process of designing a new chip or in implementing its manufacture, to determine, if possible, the maximum clock frequency at which the chip will operate. Obviously, if the maximum operating frequency can be determined at the analytical design point, before a significant investment in the manufacturing line has been made, a great deal of money can be saved by redesign, if the chip, when manufactured, will not operate properly at the frequency required. And even if, at a subsequent point in the process, the design must be alteredxe2x80x94or even abandoned and replaced with an entirely new projectxe2x80x94this might ultimately prove to be a prudent investment.
Additionally, although such cost savings can be easily appreciated in respect to a VLSI chip with millions of active components and interconnects, the potential savings which can thus be realized in the case of even a relatively simple Integrated Circuit (IC), incorporating only thousands of elements, can likewise be quite significant.
Therefore, there is a need to effectively determine, at a preliminary design phase, if possible, the extent to which a proposed chipxe2x80x94of whatever level of complexityxe2x80x94can be driven at or above the required clock frequency. This requires analysis of the time delayxe2x80x94from selected input to selected output pointsxe2x80x94of a signal input to the chip. In other words, it is necessary to determine the voltage response as a function of time.
One source of considerable transmission delay is the interconnects between active elements. Although it would be ideal if interconnects were loss-freexe2x80x94i.e., totally devoid of impedancexe2x80x94this is, unfortunately, not the case in the real world. Each interconnect does demonstrate a degree of resistance, capacitance, and, to a considerably lesser degree, inductance. While such impedance might be almost negligible in a single interconnect, even an extremely small value will have a significant effect on the maximum response speed of the circuit. Collectively, the delay caused by possibly millions of such interconnects will have a profound effect on reducing the maximum operating efficiency. In fact, interconnect delays represent an increasingly dominant portion of overall circuit delays in deep-submicron integrated circuit design.
In order to effectively predict the effect of interconnect delay, several methods have been employed by circuit designers. Because an exact solution of the time delays in interconnects requires the solution of a set of complex differential equations, circuit designers rely upon simplifications and modeling to come up with timing estimates. A commonly used model represents interconnects as resistors and capacitances in series and parallel. This model produces an RC (Resistance-Capacitance) tree, as shown in FIG. 1.
An RC tree, or any net topology tree, is generated from a design model, a directed graph representing the xe2x80x9cnetlistxe2x80x9d of the logic design. Each pin in an IC is associated with a xe2x80x9ccellxe2x80x9d. Each cell has an associated location, the x,y coordinates of the cell in the IC. Also associated with each cell is physical information which provides the cell dimensions and the pin offsets relative to the cell origin. The cell location and pin offsets may be combined to determine the locations of each source and sink pin on a net. A net topology tree may then be generated from this data. The tree may be estimated using, for example, a minimum Steiner tree. Or, an actual or preferred wire route produced by a routing tool may be used. Once a tree has been generated, an interconnect delay estimator may use that tree to perform its calculations. C and R for each segment of the tree are computed using a set of technology constants specifying the capacitance and resistance per unit length. There may be only a single set of constants for all wires in any direction, or there may be different sets of constants for horizontal and vertical wires or for wires on different wiring planes.
Once an RC tree representation has been made, circuit designers use a simplified estimation metric to calculate the time delay. Among these simplified estimation metrics, the lumped RC delay and Elmore delay metrics are some of the most widely used techniques. These techniques will be described below.
Lumped RC Delay Model
The lumped RC delay model is a highly simplified estimation metric of the interconnect delay. It is well known that the response of a simple RC circuit to a step function is given as V(t)=V0(1xe2x88x92exe2x88x92t/RC). This implies that the step input delay through the 50% point (V0/2 ) of the output waveform for a simple RC circuit is given as 0.7*RC. This delay metric represents the time constant (0.7) obtained by multiplying the total wire resistance from source to sink with the total net capacitance (RC).
For example, for the RC tree shown in FIG. 1, total resistance from source S to node 7 is R1+R2+R4+R7 and the total lumped net capacitance is Ctotal=(CS+C1+C2+C3+C4+C5+C6+C7). Thus, the interconnect delay from source S to node 7 according to lumped RC delay metric is given as 0.7*(R1+R2+R4+R7)*Ctotal. Similarly, the lumped RC delay from source to various nodes is given as follows (where TSxe2x88x921 is the delay time from source S to node 1):
TSxe2x88x921=0.7*(R1)*(Ctotal)
TSxe2x88x922=0.7*(R1+R2)*(Ctotal)
TSxe2x88x923=0.7*(R1+R3)*(Ctotal)
TSxe2x88x924=0.7*(R1+R2+R4)*(Ctotal)
TSxe2x88x925=0.7*(R1+R3+R5)*(Ctotal)
TSxe2x88x926=0.7*(R1+R3+R6)*(Ctotal)
TSxe2x88x927=0.7*(R1+R2+R4+R7)*(Ctotal)
Although the lumped RC delay model is computationally very efficient, it is highly inaccurate as compared to real interconnect delays.
Elmore Delay Model
One of the most popular delay metrics for RC trees has been the Elmore delay model because of its simplicity and high degree of correlation to real delays. Elmore originally estimated the 50% delay of a monotonic step response by the mean of the impulse response. W. C. Elmore, xe2x80x9cThe Transient Response of Damped Linear Networks with Particular Regard to Wide-band Amplifiersxe2x80x9d, Journal of Applied Physics, Vol.19, pp. 55-63, January 1948. Penfield and Rubenstein proved that the response of a general RC tree to a step input is monotonic. J. Rubinstein, Penfield, and M. A. Horowitz, xe2x80x9cSignal Delay in RC tree networksxe2x80x9d, IEEE Transactions on CAD, Vol. 2, pp. 202-211, July 1983. They utilized the Elmore delay for obtaining bounds on the step response waveform of an RC tree. Under Elmore delay, the signal delay Tsxe2x88x92i from source S to some node i in the interconnect RC tree is given as:
      T          s      -      i        =            ∑                        over          xe2x80x94                ⁢                  all          xe2x80x94                ⁢                  nodes          xe2x80x94                ⁢        k              ⁢          xe2x80x83        ⁢                  R                  k          ,          i                    ⁢              C        k            
where Ck represents the capacitance at node k; and Rk,i represents the summation of all the resistances that are common between the path from source S to node i, and the path from source S to node k. For example, in the interconnect RC tree in FIG. 1, R6,3 is given by R1+R3.
Referring to the example RC interconnect tree shown in FIG. 1, the Elmore delay from the source S to various nodes in the RC tree is given as follows:
TSxe2x88x921=R1*(C1+C2+C3+C4+C5+C6+C7)
TSxe2x88x922=TSxe2x88x921+R2*(C2+C4+C7)
TSxe2x88x923=TSxe2x88x922+R3*(C3+C5+C6)
TSxe2x88x924=TSxe2x88x922+R4*(C4+C7)
TSxe2x88x925=TSxe2x88x923+R5*(C5)
TSxe2x88x926=TSxe2x88x923+R6*(C6)
TSxe2x88x927=TSxe2x88x924+R7*(C7)
It is well known that computation of interconnect delays using the Elmore approach is very fast since it relies on single topological traversal of the interconnect tree. However, the Elmore model can result in highly inaccurate delays, especially in the case of deep-submicron designs where slews (or delay time) and resistive shielding have a significant effect on the interconnect delays.
Lastly, it should be noted that the Elmore delay represents the first moment of the impulse response, and that utilizing higher order moments can yield much better delay accuracy than the Elmore delay. For instance, Pillage et al. have utilized delay computation using higher order moments and moment-matching approximations to obtain more accurate delay estimates in RC trees. L. T. Pillage, R. A. Rohrer, xe2x80x9cAsymptotic Waveform Evaluation for Timing Analysisxe2x80x9d, IEEE Transactions on CAD, Vol. 9, April 1990. Unfortunately, these delay estimations are computationally very intensive and require large run-times. Due to the high computational complexity of obtaining higher order moments and a lack of an accurate but efficient delay metric, the Elmore delay has remained a popular delay metric for higher levels of design stages.
Therefore, there is a need for a new computationally efficient and accurate calculation method and system for estimating delays in an IC using RC (i.e., interconnect) trees. Furthermore, there is a need for a estimation method and system which considers the effect of slew as well as resistive shielding of capacitance to yield more accurate delays for both the interconnects and the driver (transistor gate). Further still, there is a need for an estimation method and system which fulfills the above-mentioned needs and is computationally as efficient as the Elmore delay calculation.
An aspect of this invention is to provide a system and method for estimating interconnect delay times in an IC using an RC tree.
Another aspect of the invention is to provide a system and method for estimating interconnect delay times using an RC tree, where the system and method considers the effect of slew as well as the resistive shielding of capacitance.
Yet another aspect of the invention is to provide a system and a method for estimating interconnect delay times using an RC tree, where the system and method consider the effect of slew as well as the resistive shielding of capacitance, and further where the system and method are as efficient computationally as the Elmore delay method.
To accomplish the above and other aspects, a method and system are proposed, which, in the preferred embodiment, estimates interconnect delay in an Integrated Circuit (IC). First, a formula for effective capacitance is derived which considers the effect of slew as well as resistive shielding of capacitance, thus yielding more accurate delays for both the interconnects and the source driver (transistor gate). Next the system and method are described, where a resistor-capacitor (RC) tree model is used for iterative calculations of effective capacitance and slew for each RC tree node. The effective capacitance is determined for each node by proceeding outward from the source to the sinks, and the slew for each node is determined, using the effective capacitances just determined, by proceeding inward from the sinks to the source node. Once the source node slew determined at a previous iteration is within a specified threshold of the source node slew in the present iteration, the method stops and stores the present iteration values as the final estimates.